﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace 图解算法数据结构._35_CopyRandomList
{

    public class Node
    {
        public int val;
        public Node next;
        public Node random;

        public Node(int _val)
        {
            val = _val;
            next = null;
            random = null;
        }
    }
    class MainProject
    {
        static void Main(string[] args)
        {
            Node node1 = new Node(7);
            Node node2 = new Node(13);
            node2.random = node1;

            Node node5 = new Node(1);
            node5.random = node1;

            Node node3 = new Node(11);
            node3.random = node5;

            Node node4 = new Node(10);
            node4.random = node3;

            node1.next = node2;
            node2.next = node3;
            node3.next = node4;
            node4.next = node5;


            CopyRandomList(node1);
            Console.WriteLine("执行到这了");
            Console.ReadKey();
        }
        public static Node CopyRandomList(Node head)
        {
            #region 哈希表
            if (head == null) return null;
            Dictionary<Node, Node> nodes = new Dictionary<Node, Node>();

            Node cur = head;

            while (cur!=null)
            {
                nodes.Add(cur,new Node(cur.val));
                cur = cur.next;
            }

            cur = head;

            while (cur != null)
            {
                if (cur.next != null) nodes[cur].next = nodes[cur.next];
                if (cur.random!=null) nodes[cur].random = nodes[cur.random];
                cur = cur.next;
            }

            return nodes[head];
            #endregion





        }
    }
}
